package org.hot100_3;

import java.util.HashMap;

public class leetcode146 {
    class LRUCache {

        class Node {
            Node pre;
            Node next;
            int val;
            int key;

            public Node(int key,int val) {
                this.key=key;
                this.val = val;
            }
            public Node(){}
        }

        final int capacity;

        Node dummy;

        HashMap<Integer, Node> hashMap = new HashMap<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummy = new Node();
            dummy.next=dummy;
            dummy.pre=dummy;
        }

        public int get(int key) {
            Node node = getNode(key);
            if (node==null){
                return -1;
            }else {
                return node.val;
            }
        }

        public void put(int key, int value) {
            Node node = getNode(key);
            if (node!=null){
                node.val=value;
                return;
            }
            Node newNode = new Node(key,value);
            hashMap.put(key,newNode);
            putNodeFirst(newNode);
            if (hashMap.size()>capacity){
               hashMap.remove(dummy.pre.key);
               removeNode(dummy.pre);
            }

        }

        private Node getNode(int key) {
            Node node = hashMap.get(key);
            if (node == null) {
                return null;
            }
            removeNode(node);
            putNodeFirst(node);
            return node;
        }


        private void putNodeFirst(Node node) {
            node.next=dummy.next;
            node.pre=dummy;

            dummy.next.pre=node;
            dummy.next=node;
        }

        private void removeNode(Node node){
            node.pre.next=node.next;
            node.next.pre=node.pre;
        }
    }
}
